package experiment4.knapsack;

import java.util.ArrayList;

public class DynamicKnapsack {
    int[][] dp;
    private ArrayList<Goods> goodsArrayList;
    boolean[] resultVector;
    private int capacity;

    public int solution(ArrayList<Goods> goodsArrayList, int capacity) {
        this.goodsArrayList = new ArrayList<>();
        this.capacity = capacity;
        for (int i = 0;i < goodsArrayList.size();i++){
            this.goodsArrayList.add(goodsArrayList.get(i));
        }

        dp = new int[goodsArrayList.size()+1][capacity+1];
        for (int i = 1; i <= goodsArrayList.size(); i++)
        {
            Goods goods = goodsArrayList.get(i-1);
            for (int j = 1; j <= capacity; j++)
            {
                //如果不取第i个物品，则总价值和dp[i-1][j]时相同
                dp[i][j] = dp[i - 1][j];
                if (j >= goods.weight)
                { //如果要取第i个物品
                    //取了之后背包容量会变为j-w[i],j-w[i]时的总价值最大值为dp[i-1][j-w[i]],此值已在只有i-1个物品时求得
                    //转移方程为不取第i个物品和取第i个物品之中的价值最大值
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - goods.weight] + goods.value);
                }
            }
        }

        resultVector = new boolean[goodsArrayList.size()];
        for (int i = goodsArrayList.size(); i >= 1; i--)
        {
            if (dp[i][capacity] == dp[i - 1][capacity])
                resultVector[i-1] = false;
            else
            {
                resultVector[i-1] = true;
                capacity = capacity - goodsArrayList.get(i-1).weight;
            }
        }
        return dp[goodsArrayList.size()][this.capacity];
    }



    public boolean[] solutionVector() {
        return resultVector;
    }
}

